package 二叉树;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

public class No116填充每个节点的下一个右侧节点指针 {

    /**
     * 给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
     * struct Node {
     *   int val;
     *   Node *left;
     *   Node *right;
     *   Node *next;
     * }
     * 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
     * 初始状态下，所有 next 指针都被设置为 NULL。
     *
     * 进阶：
     * 你只能使用常量级额外空间。
     * 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
     *  
     * 示例：
     * 输入：root = [1,2,3,4,5,6,7]
     * 输出：[1,#,2,3,#,4,5,6,7,#]
     * 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。
     *  
     * 提示：
     * 树中节点的数量少于 4096
     * -1000 <= node.val <= 1000
     */

    //是完美二叉树,所以可以不使用队列,层级必连接
    public Node connectBad(Node root) {

        LinkedList<Node> queue=new LinkedList<>();

        queue.addLast(root);

        while (!queue.isEmpty()){

            int count=queue.size();
            Node lastNode=null;

            while (count>0){

                Node node = queue.pollFirst();

                if(lastNode!=null){
                    lastNode.next=node;
                }

                if(node!=null) {
                    queue.addLast(node.left);
                    queue.addLast(node.right);
                }

                lastNode=node;
                count--;
            }

        }

        return root;
    }

    //中等解法,因为有栈的调用空间消耗
    public Node connectMid(Node root) {
        dfs(root);
        return root;
    }

    private void dfs(Node node) {

        if(node==null||node.left==null){
            return;
        }

        node.left.next = node.right;

        //妙诀在此
        if(node.next!=null){
            node.right.next=node.next.left;
        }

        dfs(node.left);
        dfs(node.right);

    }

    //最优解法 迭代法
    public Node connectGood(Node root) {

        //横着过去
        Node head=root;

        while (head!=null){

            Node cur=head;

            while (cur!=null&&cur.left!=null){

                //本节点横向链接
                cur.left.next=cur.right;

                //跨点连接
                if(cur.next!=null){
                    cur.right.next=cur.next.left;
                }

                //然后向右移动
                cur=cur.next;

            }

            head=head.left;

        }

        return root;
    }

    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    }

}
